﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Percolation
{
    [Serializable]
    public sealed class EdgeWeightSettings
    {
        public int WhiteToBlackTop { get; set; }
        public int WhiteToWhiteTop { get; set; }

        public int BlackToBlackTop { get; set; }
        public int BlackToWhiteTop { get; set; }

        public int WhiteToBlackLeft { get; set; }
        public int WhiteToWhiteLeft { get; set; }

        public int BlackToBlackLeft { get; set; }
        public int BlackToWhiteLeft { get; set; }

        public int WhiteToBlackRight { get; set; }
        public int WhiteToWhiteRight { get; set; }

        public int BlackToBlackRight { get; set; }
        public int BlackToWhiteRight { get; set; }

        public EdgeWeightSettings()
        {
            BlackToBlackTop = 0;
            BlackToWhiteTop = 1;

            WhiteToBlackTop = 0;
            WhiteToWhiteTop = 1;

            BlackToBlackLeft = 0;
            BlackToWhiteLeft = 1;

            WhiteToBlackLeft = 0;
            WhiteToWhiteLeft = 1;

            BlackToBlackRight = 0;
            BlackToWhiteRight = 1;

            WhiteToBlackRight = 0;
            WhiteToWhiteRight = 1;

        }
    }

    [Serializable]
    public sealed class NetPath
    {
        [Serializable]
        public class Cell
        {
            public int X {get; private set; }
            public int Y {get; private set; }
            public int Color {get; private set; }

            public Cell(int x, int y, int color)
            {
                X = x;
                Y = y;
                Color = color;
            }
        }

        public NetPath(List<KeyValuePair<int, int>> path, NetInterface net)
        {
            Cells = new List<Cell>();
            path.ForEach(pair => {
                if (pair.Key != -1 && pair.Value != -1)
                    Cells.Add(new Cell(pair.Key, pair.Value, net.getValue(pair.Key, pair.Value)));
                }
            );
        }

        public List<Cell> Cells { get; private set; }
    }

    [Serializable]
    public class NetPathStatistics
    {
        public int AddedCellsCount { get; private set; }
        public int RouteLength { get; private set; }
        public double AvgRouteClusters { get; private set; }
        public int MaxRouteClusters { get; private set; }
        public double AddedCellsConcentration { get; private set; }

        public NetPathStatistics(NetPath path)
        {
            List<int> routeClustersArray = new List<int>();
            bool LastBlack = false;
            int clustersRouteLen = 0;

            RouteLength = path.Cells.Count;
            AddedCellsCount = 0;
            MaxRouteClusters = 0;
            AvgRouteClusters = 0;
            path.Cells.ForEach(c =>
                {
                    if (c.Color == NetCellColor.Black)
                    {
                        if (!LastBlack)
                        {
                            if (clustersRouteLen > 0)
                                routeClustersArray.Add(clustersRouteLen);

                            LastBlack = true;
                        }
                    }
                    else if (c.Color == NetCellColor.White)
                    {
                        ++AddedCellsCount;
                        if (LastBlack)
                        {
                            clustersRouteLen = 0;
                            LastBlack = false;
                        }

                        ++clustersRouteLen;
                    }
                }
            );

            if (routeClustersArray.Count > 0)
            {
                MaxRouteClusters = routeClustersArray.Max();
                AvgRouteClusters = routeClustersArray.Average();
            }

            AddedCellsConcentration = (double) AddedCellsCount / (double) RouteLength;
        }
    }

    [Serializable]
    public class BoltStatistics
    {
        public List<KeyValuePair<NetPath, NetPathStatistics>> PathStatisticsList { get; private set; }

        public BoltStatistics(List<NetPath> pathList)
        {
            PathStatisticsList = new List<KeyValuePair<NetPath, NetPathStatistics>>();
            pathList.ForEach(p =>
                PathStatisticsList.Add(new KeyValuePair<NetPath, NetPathStatistics>(p, new NetPathStatistics(p))));
        }
    }

    public sealed class NetGraph
    {
        private struct Node
        {
            public int Distance { get; set; }
            public int Previous { get; set; }
        }

        private Node [] m_nodes = null;
        private NetInterface m_net;
        private EdgeWeightSettings m_settings;

        private int getLeftWeight(int x, int y)
        {
            bool blackSource = (m_net.getValue(x, y) == NetCellColor.Black);
            bool blackDest = (m_net.getValue(x - 1, y) == NetCellColor.Black);
            if (blackSource)
                return blackDest ? m_settings.BlackToBlackLeft : m_settings.BlackToWhiteLeft;
            else
                return blackDest ? m_settings.WhiteToBlackLeft : m_settings.WhiteToWhiteLeft;
        }

        private int getRightWeight(int x, int y)
        {
            bool blackSource = (m_net.getValue(x, y) == NetCellColor.Black);
            bool blackDest = (m_net.getValue(x + 1, y) == NetCellColor.Black);
            if (blackSource)
                return blackDest ? m_settings.BlackToBlackRight : m_settings.BlackToWhiteRight;
            else
                return blackDest ? m_settings.WhiteToBlackRight : m_settings.WhiteToWhiteRight;
        }

        private int getTopWeight(int x, int y)
        {
            bool blackSource = (m_net.getValue(x, y) == NetCellColor.Black);
            bool blackDest = (m_net.getValue(x, y - 1) == NetCellColor.Black);
            if (blackSource)
                return blackDest ? m_settings.BlackToBlackTop : m_settings.BlackToWhiteTop;
            else
                return blackDest ? m_settings.WhiteToBlackTop : m_settings.WhiteToWhiteTop;
        }

        public NetGraph(NetInterface net, EdgeWeightSettings settings)
        {
            m_net = net;
            m_settings = settings;

            int netWidth = net.getWidth();
            int netHeight = net.getHeight();

            m_nodes = new Node [netWidth * netHeight + 1];

            m_nodes[0].Distance = 0;
            m_nodes[0].Previous = Int32.MinValue;

            for (int i = 0; i < net.getWidth(); ++i)
            {
                for (int j = 0; j < net.getHeight(); ++j)
                {
                    int index = j * netWidth + i + 1;
                    m_nodes[index].Distance = Int32.MaxValue; 
                    m_nodes[index].Previous = -1;
                }
            }
        }


        public void searchDijkstra()
        {
            List<int> unvisitedNodes = new List<int>();
            for (int i=0; i<m_nodes.Count(); ++i)
                unvisitedNodes.Add(i);

            while (unvisitedNodes.Count > 0)
            {
                Node node = new Node();
                int nodeIndex = -1;
                int minDistance = Int32.MaxValue;
                unvisitedNodes.ForEach(n =>
                    {
                        if (m_nodes[n].Distance < minDistance)
                        {
                            node = m_nodes[n];
                            nodeIndex = n;
                            minDistance = node.Distance;
                        }
                    }
                );

                if (node.Distance == Int32.MaxValue)
                    break;

                unvisitedNodes.RemoveAt(unvisitedNodes.FindIndex(n => nodeIndex == n));

                if (nodeIndex == 0)
                {
                    for (int x = 0; x < m_net.getWidth(); ++x)
                    {
                        int neigborIndex = (m_net.getHeight() - 1) * m_net.getWidth() + x + 1;
                        int weight = -1;
                        if (m_net.getValue(x, m_net.getHeight() - 1) == NetCellColor.Black)
                            weight = m_settings.BlackToBlackTop;
                        else
                            weight = m_settings.BlackToWhiteTop;

                        int distance = m_nodes[nodeIndex].Distance + weight;
                        if (m_nodes[neigborIndex].Distance > distance)
                        {
                            m_nodes[neigborIndex].Distance = distance;
                            m_nodes[neigborIndex].Previous = nodeIndex;
                        }
                    }                    
                }
                else
                {
                    int x = (nodeIndex - 1) % m_net.getWidth();
                    int y = (nodeIndex - 1) / m_net.getWidth();

                    // left cell
                    if (x > 0)
                    {
                        int leftNodeIndex = nodeIndex - 1;
                        int distance = m_nodes[nodeIndex].Distance + getLeftWeight(x, y);
                        if (m_nodes[leftNodeIndex].Distance > distance)
                        {
                            m_nodes[leftNodeIndex].Distance = distance;
                            m_nodes[leftNodeIndex].Previous = nodeIndex;
                        }
                    }

                    // right cell
                    if (x < m_net.getWidth() - 1)
                    {
                        int rightNodeIndex = nodeIndex + 1;
                        int distance = m_nodes[nodeIndex].Distance + getRightWeight(x, y);
                        if (m_nodes[rightNodeIndex].Distance > distance)
                        {
                            m_nodes[rightNodeIndex].Distance = distance;
                            m_nodes[rightNodeIndex].Previous = nodeIndex;
                        }
                    }

                    // top cell
                    if (y > 0)
                    {
                        int topNodeIndex = nodeIndex - m_net.getWidth();
                        int distance = m_nodes[nodeIndex].Distance + getTopWeight(x, y);
                        if (m_nodes[topNodeIndex].Distance > distance)
                        {
                            m_nodes[topNodeIndex].Distance = distance;
                            m_nodes[topNodeIndex].Previous = nodeIndex;
                        }
                    }
                }
            }
        }

        public int getAddedCellCount(NetPath path)
        {
            int count = 0;
            path.Cells.ForEach(cell =>
                {
                    if (m_net.getValue(cell.X, cell.Y) == NetCellColor.White)
                        ++count;
                }
            );

            return count;
        }

        public NetPath getPath(int x, int y)
        {
            List<KeyValuePair<int, int>> path = new List<KeyValuePair<int, int>>();

            Node endNode = m_nodes[y * m_net.getWidth() + x + 1];
            if (endNode.Distance != Int32.MaxValue)
            {
                Node n = endNode;
                int index = y * m_net.getWidth() + x + 1;
                while (n.Previous != Int32.MinValue)
                {
                    path.Add(new KeyValuePair<int, int>((index - 1) % m_net.getWidth(), (index - 1) / m_net.getWidth()));
                    index = n.Previous;
                    n = m_nodes[n.Previous];
                }

            }

            path.Reverse();
            return new NetPath(path, m_net);
        }

    }


    public static class DijkstraSearch
    {
        public class NetPathComparer : IComparer<NetPath>
        {
            public NetPathComparer(NetGraph graph)
            {
                m_graph = graph;
            }

            public int Compare(NetPath p1, NetPath p2)
            {
                int v1 = m_graph.getAddedCellCount(p1);
                int v2 = m_graph.getAddedCellCount(p2);
                if (v1 == v2)
                    return p1.Cells.Count - p2.Cells.Count;

                return v1 - v2;
            }

            private NetGraph m_graph;
        }

        public static BoltStatistics search(NetInterface net, EdgeWeightSettings settings)
        {
            List<NetPath> pathList = new List<NetPath>();

            NetGraph graph = new NetGraph(net, settings);
            graph.searchDijkstra();

            for (int i = 0; i < net.getWidth(); ++i)
            {
                NetPath path = graph.getPath(i, 0);
                if (path.Cells.Count > 0)
                    pathList.Add(path);
            }

            pathList.Sort(new NetPathComparer(graph));

            return new BoltStatistics(pathList);
        }

    }
}
